import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-24
 * Time: 15:18
 */

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}
//class Solution {
//    public List<List<Integer>> pathSum(TreeNode root
//            , int targetsum) {
//        List<List<Integer>> res = new ArrayList<>();
//        if (root == null) return res; // 非空判断
//        List<Integer> path = new LinkedList<>();
//        preorderdfs(root, targetsum, res, path);
//        return res;
//    }
//    public void preorderdfs(TreeNode root,
//                            int targetsum,
//        List<List<Integer>> res, List<Integer> path) {
//        path.add(root.val);//利用一维数组来存储值
//        // 遇到了叶子节点
//        if (root.left == null && root.right == null) {
//            // 找到了和为 targetsum 的路径
//            if (targetsum - root.val == 0) {
//                res.add(new ArrayList<>(path));
//            }
//            return; // 如果和不为 targetsum，返回
//        }
//
//        if (root.left != null) {
//            preorderdfs(root.left,
//             targetsum - root.val, res, path);
//            path.remove(path.size() - 1); // 回溯
//        }
//        if (root.right != null) {
//            preorderdfs(root.right,
//            targetsum - root.val, res, path);
//            path.remove(path.size() - 1); // 回溯
//        }
//    }
//}

// class Solution {
//     public List<List<Integer>> pathSum(TreeNode root, int targetsum) {
//         List<List<Integer>> res = new ArrayList<>();
//         if (root == null) return res; // 非空判断
//         List<Integer> path = new LinkedList<>();
//         preorderdfs(root, targetsum, res, path);
//         return res;
//     }
//     public void preorderdfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {
//         path.add(root.val);//利用一维数组来存储值
//         // 遇到了叶子节点
//         if (root.left == null && root.right == null) {
//             // 找到了和为 targetsum 的路径
//             if (targetsum - root.val == 0) {
//                 res.add(new ArrayList<>(path));
//             }
//             return; // 如果和不为 targetsum，返回
//         }

//         if (root.left != null) {
//             preorderdfs(root.left, targetsum - root.val, res, path);
//             path.remove(path.size() - 1); // 回溯
//         }
//         if (root.right != null) {
//             preorderdfs(root.right, targetsum - root.val, res, path);
//             path.remove(path.size() - 1); // 回溯
//         }
//     }
// }

// // 解法2
// class Solution {
//     List<List<Integer>> result;
//     LinkedList<Integer> path;
//     public List<List<Integer>> pathSum (TreeNode root,int targetSum) {
//         result = new LinkedList<>();
//         path = new LinkedList<>();
//         travesal(root, targetSum);
//         return result;
//     }
//     private void travesal(TreeNode root,  int count) {
//         if (root == null) return;
//         path.offer(root.val);
//         count -= root.val;
//         if (root.left == null && root.right == null && count == 0) {
//             result.add(new LinkedList<>(path));
//         }
//         travesal(root.left, count);
//         travesal(root.right, count);
//         path.removeLast(); // 回溯
//     }
// }

class Solution {
    StringBuilder sb = new StringBuilder();
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        dfs(list,root);
        return list;
    }
    private void dfs(List<String> list ,TreeNode root){
        if(root==null) return;
        if(root.left==null&&root.right==null){
            sb.append(root.val);
            list.add(sb.toString());
            return;
        }else {
            sb.append(root.val+"->");
        }
        if(root.left!=null){
            dfs(list,root.left);
        }
        if(root.right!=null){
            dfs(list,root.right);
        }
    }
}


class Solution9 {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if(root==null) return res;
        //准备一个队列用来存放结点的值
        Queue<TreeNode> queueNode = new LinkedList<>();
        //准备一个队列用来存放路径
        Queue<String> queuePath = new LinkedList<>();
        queueNode.offer(root);
        queuePath.offer(Integer.toString(root.val));
        while(!queueNode.isEmpty()){
            TreeNode curNode = queueNode.poll();
            String curPath = queuePath.poll();
            //当我们遍历到叶子结点的时候就出现了一个路径我们就把它加到结果里
            if(curNode.left==null&&curNode.right==null){
                res.add(curPath);
            }else {
                //此时我们如果不是叶子结点证明有左孩子和右孩子，路径还没有结束需要延长路径
                if(curNode.left!=null){
                    //此时还有我们的左孩子，那我们就把它加入带队列当中去，并且加入到路径当中去
                    queueNode.offer(curNode.left);
                    //将当前结点左孩子的值拼接在一起并且转化成字符串加入到路径当中去
                    StringBuilder sb = new StringBuilder(curPath);
                    sb.append("->");
                    sb.append(curNode.left.val);
                    String newPath = sb.toString();
                    queuePath.offer(newPath);
                }

                if(curNode.right!=null){
                    //此时还有我们的右孩子，那我们就把它加入带队列当中去，并且加入到路径当中去
                    queueNode.offer(curNode.right);
                    //将当前结点左孩子的值拼接在一起并且转化成字符串加入到路径当中去
                    StringBuilder sb = new StringBuilder(curPath);
                    sb.append("->");
                    sb.append(curNode.right.val);
                    String newPath = sb.toString();
                    queuePath.offer(newPath);
                }
            }
        }
        return res;
    }
}


class Solution4 {
    public int minDepth(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int min =1;
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            int sz = queue.size();
            while(sz>0){
                //当我们每一次遍历到叶子结点的时候就记录它的深度
                if(cur.left==null&&cur.right==null){
                    return min;
                }
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                sz--;
            }
            min++;
        }
        return min;
    }
}
public class TestDemo {

    public static void main(String[] args) {
        Solution4 solution4 = new Solution4();
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(5);
        node1.right = node2;
        node2.right = node3;
        node3.right = node4;
        solution4.minDepth(node1);
    }


}
class Solution0 {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        dfs(root,result,"");
        return result;
    }

    private  void dfs(TreeNode root,List<String> result,String path){
        if(root!=null){
            StringBuilder sb = new StringBuilder(path);
            sb.append(Integer.toString(root.val));
            if(root.left==null&&root.right==null){
                result.add(sb.toString());
            }else {
                sb.append("->");
                dfs(root.left,result,sb.toString());
                dfs(root.right,result,sb.toString());
            }
        }
    }
}